package com.lin.codesnippet.sort;

import com.lin.enums.codesnippet.SortStatusCode;
import com.lin.codesnippet.sort.util.SortUtil;

/**
 * 快速排序
 * <p>O(nlogn)~O(nlogn)~O(n^2)</p>
 * 不稳定
 *
 * @author linqiankun
 */
public class QuickSort {


    /**
     * 分治块
     *
     * @param array          分治数组
     * @param left           左边界
     * @param right          右边界
     * @param sortStatusCode 排序方式
     * @return 基准的索引
     */
    private static int partition(int[] array, int left, int right, SortStatusCode sortStatusCode)  // 划分函数
    {
        // 这里每次都选择最后一个元素作为基准
        int pivot = array[right];
        // tail为小于基准的子数组最后一个元素的索引
        int tail = left - 1;
        // 遍历基准以外的其他元素
        for (int i = left; i < right; i++) {
            // 把小于等于基准的元素放到前一个子数组末尾
            //会破环稳定性
            if (SortUtil.compare(pivot, array[i]) == 0 || (sortStatusCode.getCode() != SortUtil.compare(pivot, array[i])))
            // if (array[i] <= pivot)
            {
                SortUtil.swap(array, ++tail, i);
            }
        } // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
        // 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
        SortUtil.swap(array, tail + 1, right);
        // 返回基准的索引
        return tail + 1;
    }


    /**
     * 快速排序
     *
     * @param array          排序数组
     * @param left           左边界
     * @param right          右边界
     * @param sortStatusCode 排序方式
     */
    public static void quickSorted(int[] array, int left, int right, SortStatusCode sortStatusCode) {
        if (left >= right) {
            return;
        }
        // 基准的索引
        int pivotIndex = partition(array, left, right, sortStatusCode);
        quickSorted(array, left, pivotIndex - 1, sortStatusCode);
        quickSorted(array, pivotIndex + 1, right, sortStatusCode);
    }


}
